﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
//https://leetcode.cn/problems/middle-of-the-linked-list/description/



struct ListNode {
      int val;
      struct ListNode *next;
};
typedef struct ListNode ListNode;

struct ListNode* middleNode(struct ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
//4.输入一个链表，输出该链表中倒数第k个结点
//https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
typedef struct ListNode ListNode;

int kthToLast(struct ListNode* head, int k) {
 
    ListNode* l1 = NULL;
    ListNode* l2 = head;
    ListNode* l3 = head->next;
    while (l3)
    {
        
        l2->next = l1;
        l1 = l2;
        l2 = l3;
        l3 = l3->next;
        l2->next = l1;

    }
    while (--k)
    {
        l2 = l2->next;
    }
    int num = l2->val;
    return num;
}

//9.给定一个链表，判断链表中是否有环
//https://leetcode.cn/problems/linked-list-cycle/description/
typedef struct ListNode ListNode;

bool hasCycle(struct ListNode* head) {

    ListNode* fast = head;
    ListNode* slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
        {
            return true;
        }
    }
    return false;

}



//10.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
//https://leetcode.cn/problems/linked-list-cycle-ii/description/


typedef struct ListNode ListNode;

struct ListNode* detectCycle(struct ListNode* head) {

    ListNode* fast = head;
    ListNode* slow = head;
    ListNode* pcur = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
        {
            while (pcur!=slow)
            {
                slow = slow->next;
                pcur = pcur->next;
            }
            return pcur;
            //return true;
        }
    }

    return false;

}


//11.给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝
//https://leetcode.cn/problems/copy-list-with-random-pointer/description/


struct Node {
    int val;
    struct Node* next;
    struct Node* random;
    
};
typedef struct Node Node;

void Insert(struct Node* head)
{
    Node* pcur = head;
    while (pcur)
    {
        Node* Newnode = malloc(sizeof(Node));
        Newnode->val = pcur->val;
        Newnode->next = pcur->next;
        Newnode->random = NULL;
        pcur->next = Newnode;
        pcur = Newnode->next;
    }
}

void Cheakrandom(struct Node* head)
{
    Node* pcur = head;
    while (pcur)
    {
        Node* copy = pcur->next;
        if (pcur->random)
            copy->random = pcur->random->next;
        pcur = copy->next;
    }
}

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
    {
        return head;
    }

    Insert(head);
    Cheakrandom(head);
    Node* pcur = head->next;
    Node* phead= head->next;

    while (pcur->next)
    {
        pcur->next = pcur->next->next;
        pcur = pcur->next;
    }
    return phead;
}
